#include "stdio.h"

//二叉堆
struct Heap
{
    int* data;
    int maxLen;
    int length;
    int layer;//堆有几层
    int type; //0代表大堆 1代表小堆
};

int compare(int a,int b)
{
    return a>b?1:0;
}

Heap* newHeap(int maxLen,int type)
{
    Heap* heap=new Heap();
    heap->data=new int[maxLen];
    heap->maxLen=maxLen;
    heap->length=0;
    heap->layer=0;
    heap->type=type;
    return heap;
}

//插入元素只能在最后一层
void insertHeapItem(Heap* heap,int num,int index)
{
    if(heap->length>=heap->maxLen)
    {
        return;
    }
    if(index>heap->length||index<0)
    {
        index=heap->length;
    }

    heap->data[index]=num;
    heap->length++;
    int parent; 
    while (index>0)
    {
        parent=((index+1)>>1)-1;
        if(heap->data[index]==heap->data[parent])
        {
            break;
        }
        //儿子大于父亲 就交换位置
        if(compare(heap->data[index],heap->data[parent])^heap->type)
        {
            int tmp=heap->data[index];
            heap->data[index]=heap->data[parent];
            heap->data[parent]=tmp;
            index=parent;
        }
        else{
            break;
        }
    }
}

//替换堆中的元素
void replaceHeapItem(Heap* heap,int num,int index){
    if(index>=heap->length)
    {
        return;
    }
    int tmpIndex=index;
    int left,right;
    int maxAdr=heap->length>>1;
    heap->data[index]=num;
    while (tmpIndex<maxAdr)
    {
        left=tmpIndex*2+1;
        right=left+1;

        int compareIndex;
        if(right>=heap->length||heap->data[left]==heap->data[right]
            ||(compare(heap->data[left],heap->data[right])^heap->type))
        {
            compareIndex=left;
        }
        else{
            compareIndex=right;
        }

        if(heap->data[tmpIndex]==heap->data[compareIndex]
            ||(compare(heap->data[tmpIndex],heap->data[compareIndex])^heap->type))
        {
            break;
        }
        else{
            int tmp=heap->data[tmpIndex];
            heap->data[tmpIndex]=heap->data[compareIndex];
            heap->data[compareIndex]=tmp;
            tmpIndex=compareIndex;
        }
    }
}

//删除堆中的元素
// void removeHeapItem(Heap* heap,int index)
// {
//     int tmpIndex=index;
//     int left,right;
//     int maxAdr=heap->length>>1;
//     while (tmpIndex<maxAdr)
//     {
//         left=tmpIndex*2;
//         right=left+1;
//         if(heap->data[left]==heap->data[right])
//         {
//             heap->data[tmpIndex]=heap->data[left];
//             tmpIndex=left;
//         }
//         //左边大于等于右边
//         if(heap->data[left]==heap->data[right]||compare(heap->data[left],heap->data[right])^heap->type)
//         {
//             heap->data[tmpIndex]=heap->data[left];
//             tmpIndex=left;
//         }
//         else{
//             heap->data[tmpIndex]=heap->data[right];
//             tmpIndex=right;
//         }
//     }
//     heap->length--;
//     if(heap->length>0)
//     {
//         insertHeapItem(heap,heap->data[heap->length],tmpIndex);
//     }
// }

void printArray(int* array,int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
}


int main(){
    int center;
    int n;
    Heap* left,*right;
    scanf("%d",&n);
    int maxLen=(n>>1)+1;
    left=newHeap(maxLen,0);
    right=newHeap(maxLen,1);
    scanf("%d",&center);
    printf("%d\n",center);

    int i,tmp;
    for(i=1;i<n;i++)
    {
        scanf("%d",&tmp);
        if(tmp==center)
        {
            if(left->length<=right->length)
            {
                insertHeapItem(left,tmp,-1);
            }
            else {
                insertHeapItem(right,tmp,-1);
            }
        }
        //插入到左边 但是要保证左右堆数量的平衡
        else if(tmp<center)
        {
            if(left->length>right->length)
            {
                int num=center;
                if(tmp>=left->data[0])
                {
                    center=tmp;
                }
                else{
                    center=left->data[0];
                    replaceHeapItem(left,tmp,0);
                }
                insertHeapItem(right,num,-1);
            }
            else{
                insertHeapItem(left,tmp,-1);
            }
        }
        //插入到右边 但是要保证左右堆数量的平衡
        else{
             if(right->length>left->length)
            {
                int num=center;
                if(tmp<=right->data[0])
                {
                    center=tmp;
                }
                else{
                    center=right->data[0];
                    replaceHeapItem(right,tmp,0);
                }
                insertHeapItem(left,num,-1);
            }
            else{
                insertHeapItem(right,tmp,-1);
            }
        }

        // printf("%d: center:%d\n",i,center);
        // printArray(left->data,left->length);
        // printArray(right->data,right->length);

        if(i%2==0)
        {
            printf("%d\n",center);
        }
    }

    delete left->data;
    delete left;
    delete right->data;
    delete right;
    return 0;
}

